#include "tinyalloc.h"
#include <stdint.h>

#ifdef __cplusplus
extern "C" {
#endif

#ifdef TA_DEBUG
extern void print_s(char*);
extern void print_i(size_t);
#else
#    define print_s(X)
#    define print_i(X)
#endif

/**
 * If compaction is enabled, inserts block
 * into free list, sorted by addr.
 * If disabled, add block has new head of
 * the free list.
 * 如果内存压缩开启,内存回收时临近内存合并
 */
static void insert_block(Heap* heap, Block* block) {
#ifndef TA_DISABLE_COMPACT     //内存合并,对内存按地址大小由小到大排序,合并时可用就近进行
    Block* ptr  = heap->free;  // free指向的块永远时最小的
    Block* prev = NULL;
    while (ptr != NULL) {
        if ((size_t)block->addr <= (size_t)ptr->addr) {
            print_s("insert");
            print_i((size_t)ptr);
            break;
        }
        prev = ptr;
        ptr  = ptr->next;
    }
    if (prev != NULL) {
        if (ptr == NULL) {
            print_s("new tail");
        }
        prev->next = block;
    } else {
        print_s("new head");
        heap->free = block;
    }
    block->next = ptr;
#else
    block->next = heap->free;
    heap->free  = block;
#endif
}

#ifndef TA_DISABLE_COMPACT
// scan为释放块
static void release_blocks(Heap* heap, Block* scan, Block* to) {
    Block* scan_next;
    while (scan != to) {
        print_s("release");
        print_i((size_t)scan);
        scan_next   = scan->next;
        scan->next  = heap->fresh;
        heap->fresh = scan;  // fresh新增块
        scan->addr  = 0;
        scan->size  = 0;
        scan        = scan_next;
    }
}

static void compact(Heap* heap) {
    Block* ptr = heap->free;  //合并free内存区地址连接块
    Block* prev;
    Block* scan;
    while (ptr != NULL) {
        prev = ptr;
        scan = ptr->next;
        //两个内存块相连(free按addr由小到大排序,前一块addr+size==下一块addr)
        while (scan != NULL && (size_t)prev->addr + prev->size == (size_t)scan->addr) {
            print_s("merge");
            print_i((size_t)scan);
            prev = scan;
            scan = scan->next;
        }
        //合并匹配
        if (prev != ptr) {
            //新内存大小由高地址块减低地址块加高地址块大小
            size_t new_size = (size_t)prev->addr - (size_t)ptr->addr + prev->size;
            Block* next     = NULL;
            print_s("new size");
            print_i(new_size);
            ptr->size = new_size;    //新内存块大小修改
            next      = prev->next;  // next更新
            // make merged blocks available
            release_blocks(heap, ptr->next, prev->next);  //释放ptr->next与prev->next之间所有块到fresh
            // relink
            ptr->next = next;
        }
        ptr = ptr->next;
    }
}
#endif

bool ta_init(Heap*        heap,
             const void*  limit,
             const size_t heap_blocks,
             const size_t split_thresh,
             const size_t alignment) {
    Block* block = NULL;
    size_t i     = 0;

    heap->heap_limit        = limit;         //内存区结束地址
    heap->heap_split_thresh = split_thresh;  //内存分块最小长度
    heap->heap_alignment    = alignment;     //内存对齐大小
    heap->heap_max_blocks   = heap_blocks;   //内存块最大数量

    heap->free  = NULL;                                 //初始化时没有内存分配
    heap->used  = NULL;                                 //初始化时没有内存使用
    heap->fresh = (Block*)(heap + 1);                   //未分配内存块首地址未heap下一个字节地址
    heap->top   = (size_t)(heap->fresh + heap_blocks);  // fresh内存区起始地址,从低往高增长

    //初始化fresh Block,一共heap_max_blocks块
    block = heap->fresh;
    i     = heap->heap_max_blocks - 1;
    while (i--) {
        block->next = block + 1;
        block++;
    }
    block->next = NULL;
    return true;
}

bool ta_free(Heap* heap, void* free) {
    Block* block = heap->used;
    Block* prev  = NULL;
    //遍历已使用内存块查找到要释放内存块
    while (block != NULL) {
        //内存匹配
        if (free == block->addr) {
            //释放内存为中间块,修改上一块内存next指向
            if (prev) {
                prev->next = block->next;
            }
            //释放内存为第一块内存,修改used为下一块
            else {
                heap->used = block->next;
            }
            //将回收块插入可用区
            insert_block(heap, block);
#ifndef TA_DISABLE_COMPACT
            //临近内存碎片合并
            compact(heap);
#endif
            return true;
        }
        prev  = block;
        block = block->next;
    }
    return false;
}

static Block* alloc_block(Heap* heap, size_t num) {
    Block* ptr     = heap->free;
    Block* prev    = NULL;
    size_t top     = heap->top;
    size_t new_top = 0;
    num            = (num + heap->heap_alignment - 1) & -heap->heap_alignment;
    while (ptr != NULL) {
        //内存分配优先从used区分配
        //当前块是否为已分配内存顶部块且剩余内存满足分配(ptr->add+ptr->size==top表示与fresh块top相连,为已分配内存顶部块)
        const int is_top =
            ((size_t)ptr->addr + ptr->size >= top) && ((size_t)ptr->addr + num <= (size_t)heap->heap_limit);
        if (is_top || ptr->size >= num) {
            if (prev != NULL) {
                prev->next = ptr->next;
            } else {
                heap->free = ptr->next;
            }
            ptr->next = heap->used;  //分配内存加入used已使用内存块
            heap->used = ptr;  //修改已使用内存used指向新内存块(used指向的内存块永远都是地址最大的)
            //当前块为顶部内存块
            if (is_top) {
                print_s("resize top block");
                ptr->size = num;                      //修改内存块大小
                heap->top = (size_t)ptr->addr + num;  //修改fresh起始地址
#ifndef TA_DISABLE_SPLIT                              //内存切割为更小碎片
            } else if (heap->fresh != NULL) {
                size_t excess = ptr->size - num;  //当前内存块剩余大小
                //剩余大小大于最小片,内存分片
                if (excess >= heap->heap_split_thresh) {
                    Block* split = NULL;
                    ptr->size    = num;                               //修改内存块大小
                    split        = heap->fresh;                       //取一个未分配块存储碎片
                    heap->fresh  = split->next;                       //减小一个未分配块
                    split->addr  = (void*)((size_t)ptr->addr + num);  //更小碎片起始地址
                    print_s("split");
                    print_i((size_t)split->addr);
                    split->size = excess;       //更新碎片大小
                    insert_block(heap, split);  //将碎片插入可用内存区
#    ifndef TA_DISABLE_COMPACT
                    compact(heap);  //碎片内存块合并
#    endif
                }
#endif
            }
            return ptr;
        }
        prev = ptr;
        ptr  = ptr->next;
    }
    // no matching free blocks
    // see if any other blocks available
    //从未分配区分配内存
    new_top = top + num;
    //未分配区还有空余块且剩余内存长度还够
    if (heap->fresh != NULL && new_top <= (size_t)heap->heap_limit) {
        ptr         = heap->fresh;  //从fresh取一块未分配内存
        heap->fresh = ptr->next;    // fresh未分配内存减少一块
        ptr->addr   = (void*)top;   //修改分配内存起始地址
        ptr->next   = heap->used;   //分配内存加入used已使用内存块
        ptr->size   = num;          //修改分配内存块大小
        heap->used = ptr;  //修改已使用内存used指向新内存块(used指向的内存块永远都是地址最大的)
        heap->top = new_top;  //修改fresh未分配内存起始地址
        return ptr;
    }
    return NULL;
}

#ifdef WL_MALLOC_CHECK
void* ta_alloc_debug(Heap* heap, size_t num, char* func, size_t line) {
    Block* block = alloc_block(heap, num);
    if (block != NULL) {
        block->func = func;
        block->line = line;
        return block->addr;
    }
    return NULL;
}
#endif

void* ta_alloc(Heap* heap, size_t num) {
    Block* block = alloc_block(heap, num);
    if (block != NULL) {
        return block->addr;
    }
    return NULL;
}

static void memclear(void* ptr, size_t num) {
    uint8_t* ptrb = NULL;
    size_t*  ptrw = (size_t*)ptr;
    size_t   numw = (num & -sizeof(size_t)) / sizeof(size_t);
    while (numw--) {
        *ptrw++ = 0;
    }
    num &= (sizeof(size_t) - 1);
    ptrb = (uint8_t*)ptrw;
    while (num--) {
        *ptrb++ = 0;
    }
}

void* ta_calloc(Heap* heap, size_t num, size_t size) {
    Block* block = NULL;
    num *= size;
    block = alloc_block(heap, num);
    if (block != NULL) {
        memclear(block->addr, num);
        return block->addr;
    }
    return NULL;
}

static size_t count_blocks(Block* ptr) {
    size_t num = 0;
    while (ptr != NULL) {
        num++;
        ptr = ptr->next;
    }
    return num;
}

size_t ta_mem_size(Heap* heap, void* ptr) {
    Block* block = heap->used;
    while (block != NULL) {
        if (ptr == block->addr) {
            return block->size;
        }
        block = block->next;
    }
    return 0;
}

size_t ta_num_free(Heap* heap) {
    return count_blocks(heap->free);
}

size_t ta_num_used(Heap* heap) {
    return count_blocks(heap->used);
}

size_t ta_num_fresh(Heap* heap) {
    return count_blocks(heap->fresh);
}

size_t ta_free_size(Heap* heap) {
    size_t size  = 0;
    Block* block = heap->free;
    while (block != NULL) {
        size += block->size;
        block = block->next;
    }
    return size;
}

size_t ta_used_size(Heap* heap) {
    size_t size  = 0;
    Block* block = heap->used;
    while (block != NULL) {
        size += block->size;
        block = block->next;
    }
    return size;
}

size_t ta_fresh_size(Heap* heap) {
    return (size_t)heap->heap_limit - (size_t)(heap->top);
}

bool ta_check(Heap* heap) {
    return heap->heap_max_blocks == ta_num_free(heap) + ta_num_used(heap) + ta_num_fresh(heap);
}

#ifdef __cplusplus
}
#endif
